The present invention relates to classifying triangles into different categories for three-dimensional graphics displays.
Three-dimensional computer graphics displays are used to display images to a user as if he were observing a real world environment. These systems store in a data base a representation in three-dimensional coordinates of three-dimensional objects, as well as their color and other properties. Additional "environment" information including the number, color, location, and other properties of illumination sources, atmospheric properties, and many other details may also be specified. The display is produced after being provided with the desired viewing angle for the viewer. The system must calculate all the details of the image, including determining which objects obscure others from the viewer's point of view, and present them accordingly.
A typical graphics display system is shown in FIG. 1. An image data base 12 stores a description of the objects in the scene. The objects are described with a number of small polygons which cover the surface of the object in the same manner that a number of small tiles can cover a wall or other surface. Each polygon is described as a list of vertex coordinates (X, Y, Z in "Model" coordinates) and some specification of material surface properties (i.e., color, texture, shininess, etc.), as well as possibly the normal vectors to the surface at each vertex. For three-dimensional objects with complex curved surfaces, the polygons in general must be triangles or quadralaterals, and the latter can always be decomposed into pairs of triangles.
A transformation engine 14 transforms the object coordinates in response to the angle of viewing selected by a user from user input 16. In addition, the user may specify the field of view, the size of the image to be produced, and the back end of the viewing volume so as to include or eliminate background as desired.
Once this viewing area has been selected, a clipping circuit 18 eliminates the polygons (i.e., triangles) which are outside the viewing area and "clips" the polygons which are partly inside and partly outside the viewing area. These clipped polygons will correspond to the portion of the polygon inside the viewing area with new edge(s) corresponding to the edge(s) of the viewing area. The polygon vertices are then transmitted to the next stage in coordinates corresponding to the viewing screen (in X, Y coordinates) with an associated depth for each vertex (the Z coordinate). In a typical system, the lighting model 20 is next applied taking into account the light sources 22. The polygons with their color values are then transmitted to a rasterizer 24.
For each polygon, rasterizer 24 determines which pixel positions are covered by the polygon and attempts to write the associated color values and depth (Z value) into frame buffer 26. Rasterizer 24 compares the depth values (Z) for the polygon being processed with the depth value of a pixel which may already be written into the frame buffer. If the depth value of the new polygon pixel is smaller, indicating that it is in front of the polygon already written into the frame buffer, then its value will replace the value in the frame buffer because the new polygon will obscure the polygon previously processed and written into the frame buffer. This process is repeated until all of the polygons have been rasterized. At that point, video controller 28 displays the contents of frame buffer 26 on a display 30 a scan line at a time in raster order.
In order to aid the rasterizer in processing the polygons, the polygons are often classified by type. Where the polygons are triangles, for instance, if the triangle has a level bottom on a single scan line, the rasterizer will know that it can stop once it has reached the end of the left border, which may be marked by a change in slope. If, on the other hand, the slope of the left border changes because the triangle has a bottom at an angle, the rasterizer must keep rasterizing but with a different slope for the left boundary. If the rasterizer is provided with information on the triangle type, it will know what to do in these situations with minimal data. Typically, the classification of triangles is done by doing a series of calculations on the triangle data. For instance, the bottom two vertices may be compared to see if they are on the same scan line (same y coordinate). If not, a further test may be done to determine if one vertex is to the left of the other or to the right of the other. After passing through a series of tests, the classification of the triangle can eventually be determined.
In addition to classifying triangles, some triangles must be eliminated. For example, certain "degenerate" triangles should not be processed. Such triangles include triangles where all three vertices are on a single line, and thus the triangle is just a line. Alternately, the triangle may be so small that it does not enclose a pixel and would not show up in the display. Finally, there are "backfacing" triangles, which are triangles on the backside of a surface to be viewed. These triangles should also be eliminated since they will not be visible from a particular viewpoint. One can determine whether a triangle is backfacing if one can figure out the order of the vertices. In a typical system, the triangles are defined with the vertices in clockwise order from the viewing angle in which the triangle is visible. Thus, if a viewing angle is selected from the opposite side, where the triangle is not visible, the triangle vertices will be presented in counter-clockwise order. A determination of the clockwise or counter-clockwise nature of the data is performed to determine whether a triangle is backfacing and should be eliminated.